import com.sun.org.apache.bcel.internal.generic.SWAP;

public class Main {
    public static void main(String[] args) {
       //时间复杂度和空间复杂度
        //如何评判一个代码的效率高不高？
        //那就是
        //时间效率： 时间复杂度 (优先考虑)
        //空间效率： 空间复杂度

         //****时间复杂度****

         //通过数学函数来表示
        //定义：
        //在计算机科学中，算法的时间复杂度是一个数学函数，它定量描述了该算法的运行时间。
        //算法是可以上机测试的，一个算法所花费的世界与其中语句的 执行次数 成正比例关，算法中的基本操作的执行次数，为算法的时间复杂度
        //用执行次数最多来的反馈时间复杂度(找的是执行次数最多的呢部分)

        //函数的表示方法
        //***大O渐进表示法***
        //计算方法func1基本操作执行了多少次

        /*void func1(int N){
            int count = 0;
            for(int i = 0; i < N;i++){
                for (int j = 0; j < N; j++) {
                    count++;   //毫无疑问这个count执行的次数是最多的 （因为是在循环里面）
                    //这个时间复杂度时N个N相加 ： N的平方
                    //解释 ，因为i执行N次，每一个i都要执行N个j所以一共是N的平方次
                }
            }
            for(int k = 0 ; k < 2*N ; k++){
                count++;         //同时这个count执行的次数也是最多的
                //一共执行了2*N次
                // 这个时间复杂度是 2*N
            }

            int M = 10;
            while((M--)>0){
                count++;        //这个count执行的次数也是最多的
                //一共执行了10次
                //所以时间复杂度是 10
            }
        }
          // 所以总的下来 函数 fun1 的时间复杂度是这几个加起来
          //也就是 ： N*N+2*N+10  （这是一个比较精确的结果）
          // 但是用大O渐进法表示
          //算法的时间复杂度是一个大概值 ， 再N值很大的情况下 ， 2*N 和 10 是可以忽略不计的

           //所以实际当中 我们计算时间复杂度的时候 ，我们其实并不一定要计算准确的执行次数，而只是需要大概执行次数，
           //那么我们这里使用大O渐进法表示

           //大O渐进法的三条规则:
           //1.用常数 1 取代运行时间中 的所有加法常数。
           //2.在修改后的运行次数函数中，只保留最高阶项。
           //3.如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结构就是大O阶。
           // 用大O渐进法表示后，时间复杂度为：O(N*N);


            //假设有一个数组，在数组中查找你要找的关键字？数组长度为N
           // 最好情况下的时间复杂度: O(1)    任意输入规模的最小运行次数(下界)
           // 平均情况下的时间复杂度: O(N/2)  任意输入规模的期望运行次数  （这个一般用不到）
           // 最坏情况下的时间复杂度: O(N)    任意输入规模的最大运行次数（上界）

           //在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为：O(N)
           //那么以后在没有说明时间复杂度的情况下都是默认 最坏时间复杂度
        */
        //例题1：
      /*  void func3(int N, int M){
            int count = 0;
            for (int i = 0; i < N; i++) {
                count++;
            }
            for (int j = 0; j < M; j++) {    //是并列关系的两个count
                count++;
            }
            System.out.println(count);
        }
        时间复杂度为：O(N+M)
        */

        //列题2：
     /*   void func4(int N){
            int count = 0;
            for (int i = 0; i < 100; i++) {
                count++;
            }
            System.out.println(count);
        }
        时间复杂度是：O(1)
        */
        // N代表问题的规模
        //例题3：
        //计算bubbleSort的时间复杂度？
        /*void bubbleSort(int[] array){
            for(int end = array.length ; end>0 ; end--){  这里最坏情况是end次 相当于n次
                boolean sorted = true;
                for(int i = 1 ; i < end ;i++){  //最坏情况也是 end - 1 次 （相当于是(n-1)次）
                                                //总共被执行了 （n-1）+(n-2)+(n-3)+...+(1)   一共有n次
                    if(array[i-1]>array[i]){
                        Swap(array,i-1,i);
                        sorted = false;
                    }
                }
                if(sorted == true){
                    break;
                }
            }
        }
         //总的次数为 ：（（首项+尾项）*项数）/ 2
        //也就是: (((n-1)+(n-1))*n)/2
         //化简为： ( n^2+n^2-2n ) / 2
         //  2*(n^2 - n) / 2
          // (n^2 - n)

          //也就是总共 （n-1）* n 次
          //用等差数列求解
            最坏时间复杂度为：O(N^2) // N的平方
            最好的时间复杂度是： O(N) 因为不管怎么样至少都会遍历一边数组
            //算时间复杂的的时候不要只看代码，还要结合思想
        */

        //例题5：
        //计算二分查找的时间复杂度
    /*    int binarySearch(int[] array,int value){
            int begin = 0;
            int end = array.length - 1;
            while(begin<=end){
                int mid = (begin+end)/2;  //每一次就砍掉一半 N --> N/2
                // 剩下的一半中还需要继续折半
                // N --> N/2 --> N/4 -->...1
                //假设执行了x 次
                //呢最终结果也就是 N/2^x = 1 ;
                //2^x = N
                //x = logN ; log以二为底的N的对数

                //思想
                // 数据       次数
                //  2          2     //有两个数据的话要找2次
                //  4          3     //有四个数据的话要找3次
                //  8          4      //以此类推
                   ...
                //  N          2^(x-1) = n  // 求x  ， x = logN + 1 ;

                if(array[mid]<value) {
                    begin = mid + 1;
                }else if(array[mid]>value){
                    end = mid - 1;
                }else{
                    return mid;
                }
            }
            return -1;
        }
        时间复杂度为：O(log(N))   //log 以二为底的N的对数   //在数据结构里面log默认是以2为底的对数

        */


        //例题6：
        //递归的时间复杂度：
       /* long factorial(int N){
            return N < 2 ? N : factorial(N - 1) * N ;  // 递归的时间复杂度 =  递归的次数*每次递归后代码的执行次数
            // 每次递归后代码的执行次数 : 在这里面只进行了三目运算符 ， 而每次三目运算符的时间复杂度就是 1
            //    这里面如果有一个循环的话，呢将循环的次数，循环几次就是几（循环N次就是N，循环M次就是M）
            // 递归的次数 ： 这里面的递归次数是N次


        }
        有循环的情况下就是执行 N * N 或者 N*其他次数
        时间复杂度为：O(N) ;
        */


        // 例题7：
        // 计算斐波那契的时间复杂度
        /*int fibonacci(int N){
            return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
             // 递归的时间复杂度 =  递归的次数*每次递归后代码的执行次数
             //递归的次数*每次递归后代码的执行次数 : 这里面还是 1
             //  递归的次数 :  次

             // 例如 N = 4 的时候 ，递归次数为 7 次
             f4                               f(N)                              1项
          f3    f2                  f(N-1)            f(N-2)                    2项
        f2  f1 f1              f(N-2)    f(N-3)    f(N-3)   f(N-4)              4项
      f1                     ....                                ....           ...
                           f(1) f(1)      ...       ...          f(1) f(1)     2^(N-1)项  x
                           那么x怎么求呢：经推理可知道 x = 2^(N-1)
                           所以总共的递归次数为 ： 1+2+4+...+2^(N-1)  是一个等比数列
                          化简结果为：    1*((1-2^(N))/(1-2)) == -(1-2^N)   == 2^N - 1

        }
        时间复杂度为：O(2^N)   (2的N次方)
        */

        //***空间复杂度***
        // 空间复杂度是对一个算法在运行过程中 临时占用存储空间的大小的量度。 空间复杂度不是程序占用了多少空间，
        // 因为这个也没太大意义，所以空间复杂度算是个变量的个数。空间复杂度计算规则基本跟时间复杂度一样使用大O渐进法

        //冒泡排序的空间复杂度？上述例题3
        // 因为这个数组是不会随着问题的变化而变化的
        //所以空间复杂度是O(1)

        //计算fibonacci的空间复杂度？
        /*int[] fibonacci(int n){
            long[] fibArray = new long[n+1];  // 这里的数组是会随着 n 的变化 而变化的
            fibArray[0] = 1;
            fibArray[1] = 1;
            for (int i = 2; i < n; i++) {
                fibArray[i] = fibArray[i-1]+fibArray[i-2];
            }
            return fibArray;
        }
        这里的数组是会随着 n 的变化 而变化的
        空间复杂的为：O(N)
        */

        //计算阶乘递归的空间复杂度？
        /*long factorial(int N){
            return N<2 ? N : factorial(N-1)*N
        }
        因为每一次递归都要在栈上开辟一块内存（栈帧） ，所以有几个N就要开辟几个空间
        空间复杂度是：O(N)
        */

        //计算斐波那契递归的空间复杂度？
        /*int fibonacci(int N){
            return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
        }
        二叉树原理，就是 在计算右边的时候 左边已经走完了，走完了也就释放空间了，只会存一条边的空间
        每一个子树也都是这样算的 ，最长的一条边是N个节点
        空间复杂度是O(N)
        */

        //总结：
        //常见的复杂度的大O的渐进法表示：
        // O(1)  O(logN)  O(N)  O(NlogN)  O(N^2)  //这就是从小到大的顺序



    }
}